package code.mySpecializedTraining;

import java.util.*;

/**
 * @author 26029
 * @date 2025/4/12
 * @description
 */
public class MonoStack {
    // 739. 每日温度
    public int[] dailyTemperatures(int[] temperatures) {
        int len = temperatures.length;
        int[] nextBig = new int[len];
        Deque<Integer> mono_stack = new LinkedList<>();
        for (int i = len - 1; i >= 0; i--) {
            while (!mono_stack.isEmpty() && temperatures[i] >= temperatures[mono_stack.peek()]) {
                mono_stack.pop();
            }
            if (!mono_stack.isEmpty()) {
                nextBig[i] = mono_stack.peek() - i;
            }
            mono_stack.push(i);
        }
        return nextBig;
    }

    // 496. 下一个更大元素 I
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        // 先求nums2的nextBig数组
        int len = nums2.length;
        int[] nextBig = new int[len];
        Arrays.fill(nextBig, -1);
        Deque<Integer> mono_stack = new LinkedList<>();
        for (int i = len - 1; i >= 0; i--) {
            while (!mono_stack.isEmpty() && nums2[i] >= mono_stack.peek()) {
                mono_stack.pop();
            }
            if (!mono_stack.isEmpty()) {
                nextBig[i] = mono_stack.peek();
            }
            mono_stack.push(nums2[i]);
        }
        // 用一个map获得nums2中个元素的位置
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < len; i++) {
            map.put(nums2[i], i);
        }
        // 查找nums1中与nums2中个元素对应的nextBig
        int ansLen = nums1.length;
        int[] ans = new int[ansLen];
        for (int i = 0; i < ansLen; i++) {
            ans[i] = nextBig[map.get(nums1[i])];
        }
        return ans;
    }

    // 503. 下一个更大元素 II
    public int[] nextGreaterElements(int[] nums) {
        int len = nums.length;
        Deque<Integer> mono_stack = new LinkedList<>();
        int[] nextBig = new int[len];
        Arrays.fill(nextBig, -1);
        // 找到最大值的位置
        int max = Integer.MIN_VALUE;
        int maxPos = -1;
        for (int i = 0; i < len; i++) {
            if (nums[i] >= max) {
                max = nums[i];
                maxPos = i;
            }
        }
        int count = 0;
        int pos = maxPos;
        while (count < len) {
            while (!mono_stack.isEmpty() && nums[pos] >= mono_stack.peek())
                mono_stack.pop();
            if (!mono_stack.isEmpty())
                nextBig[pos] = mono_stack.peek();
            mono_stack.push(nums[pos]);

            pos = pos == 0 ? len - 1 : pos - 1;
            count++;
        }
        return nextBig;
    }

    // 42. 接雨水
    public int trap(int[] height) {
        int len = height.length;
        Deque<Integer> mono_stack = new LinkedList<>();
        int sum = 0;
        for (int i = 0; i < len; i++) {
            // height[i] > height[mono_stack.peek()] 还是 height[i] >= height[mono_stack.peek()] 不影响答案，因为计算答案的时候
            // 不符合的答案 int hei = Math.min(height[i], height[left]) - height[bottom]; 这一句等于0
            while (!mono_stack.isEmpty() && height[i] > height[mono_stack.peek()]) {
                // 第一个比他小的，作为底
                int bottom = mono_stack.pop();
                // 如果有第二个比他小的，才能装水，第二个作为左墙
                if (mono_stack.isEmpty())
                    break;
                int left = mono_stack.peek();
                int hei = Math.min(height[i], height[left]) - height[bottom];
                int wid = i - left - 1;
                sum += hei * wid;
            }
            mono_stack.push(i);
        }
        return sum;
    }

    // 84. 柱状图中最大的矩形
    public int largestRectangleArea(int[] heights) {
        // 对于每一个小柱子，找他左右第一个比他小的柱子，位置为posLeftSmall, posRightSmall
        // 对于这个柱子，他往左右延展的范围就是[posLeftSmall + 1, posRightSmall - 1]
        int len = heights.length;
        Deque<Integer> mono_stack = new LinkedList<>();
        int[] leftSmall = new int[len], rightSmall = new int[len];
        Arrays.fill(leftSmall, -1); // leftSmall[i]表示左面没有比他小的
        Arrays.fill(rightSmall, len); // rightSmall[i]表示右面没有比他小的
        for (int i = 0; i < len; i++) {
            while (!mono_stack.isEmpty() && heights[i] <= heights[mono_stack.peek()])
                mono_stack.pop();
            if (!mono_stack.isEmpty())
                leftSmall[i] = mono_stack.peek();
            mono_stack.push(i);
        }
        mono_stack.clear();
        for (int i = len - 1; i >= 0; i--) {
            while (!mono_stack.isEmpty() && heights[i] <= heights[mono_stack.peek()])
                mono_stack.pop();
            if (!mono_stack.isEmpty())
                rightSmall[i] = mono_stack.peek();
            mono_stack.push(i);
        }
        int maxArea = 0;
        for (int i = 0; i < len; i++) {
            maxArea = Math.max(maxArea, heights[i] * (rightSmall[i] - leftSmall[i] - 1));
        }
        return maxArea;
    }
}
